import java.util.*;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-51-N皇后
 * @date 2025/5/15 16:20
 */
public class Solution51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        int[] queen = new int[n];
        Arrays.fill(queen, -1);
        Set<Integer> col = new HashSet<>();
        Set<Integer> d1 = new HashSet<>();
        Set<Integer> d2 = new HashSet<>();
        backTrack(ans, queen, n, col, d1, d2, 0);
        return ans;
    }

    private void backTrack(List<List<String>> ans, int[] queen, int n, Set<Integer> col, Set<Integer> d1, Set<Integer> d2, int row) {
        if (row == n) {
            List<String> board = generateBoard(queen, n);
            ans.add(board);
            return;
        }
        for (int i = 0; i < n; i++) {
            // 依次遍历每一列
            if (col.contains(i)) {
                continue;
            }
            int x = row - i;
            if (d1.contains(x)) {
                continue;
            }
            int y = row + i;
            if (d2.contains(y)) {
                continue;
            }
            queen[row] = i;
            col.add(i);
            d1.add(x);
            d2.add(y);
            backTrack(ans, queen, n, col, d1, d2, row + 1);
            // 恢复现场
            queen[row] = -1;
            col.remove(i);
            d1.remove(x);
            d2.remove(y);
        }
    }

    private List<String> generateBoard(int[] queen, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] c = new char[n];
            Arrays.fill(c, '.');
            c[queen[i]] = 'Q';
            board.add(new String(c));
        }
        return board;
    }
}
